The invention relates generally to network engineering. More specifically, the invention relates to router systems and methods that reduce the amount of forwarding table state on line cards within routers. Each line card forwarding table is based on the traffic demands only it needs to support, separate from the demands on other line cards. Line cards only populate their forwarding tables for packets needed to transmit.
Today, network operators or Internet Service Providers (ISPs) are forced to periodically upgrade Internet Protocol (IP) routing equipment to keep pace with their own internal growth as well as the rest of the Internet. Day by day, IP routing tables (global Border Gateway Protocol (BGP) routing tables) that comprise the Internet are constantly growing. This growth takes a toll on network equipment regarding memory to store routing tables and forwarding tables, and the processing power to create and maintain those tables.
Routers typically contain input ports, output ports, a specialized operating system, memory, and one or more processors. Distributed routers require memory for two purposes besides the operating system itself: storing a routing table which is used to perform routing decisions, and storing a forwarding table which is used when making forwarding decisions to switch packets out on particular interfaces.
These two functions are critical to the operation of any router employed on an IP network. Without sufficient memory, a router would be unable to properly forward packets. Due to Internet growth, network operators must upgrade their equipment to handle route growth and satisfy the above two purposes. This results in a cycle where equipment must be upgraded or replaced every 3 to 5 years. Furthermore, operators encounter scenarios where their hardware cannot be upgraded any further. This is due in part that when manufactured, there were technical limits prohibiting capacity expansion. For these cases, network operators have always been faced with replacing hardware.
Routers typically include a route processor and line cards. The route processor runs the operating system of the router, is responsible for communication to line cards, provides a means for the network operator to configure and monitor the router, runs the routing protocols (e.g. Open Shortest Path First (OSPF), Intermediate System to Intermediate System (IS-IS), Border Gateway Protocol (BGP) and others) required to communicate with other routers, makes routing decisions, and stores the network routing table. Line cards contain the input/output ports which are used to physically connect to other devices in the network, and in a router with distributed forwarding, also contain forwarding tables used to make a decision on how to switch a packet from input port to output port. The route processor communicates with the line cards through a protocol which is designed by the router manufacturer. This intra-router communication is typically unique to a particular router implementation.
In a distributed router, the route processor will typically use the intra-router communication protocol to transmit the entire list of prefixes in the routing table to each line card. In this manner, every line card possesses a “full view” of the routing information, so that every line card can switch any packet in the network. However, storing the entire list of prefixes places a large memory requirement on the line cards.
Some router implementations employ a cache-based forwarding table population scheme, where all line cards possess a forwarding table which is initially empty. One line card receives a packet on an input port for which the destination address is not contained in its forwarding table. The line card queries the route processor for routing information, and the route processor responds back to all line cards with the routing information. The line card which received the packet is able to use the routing information received to switch the packet to the proper output port. However, while the line card is waiting for the route processor to respond, the first packet received and any subsequent packet received for that same destination must be buffered or dropped.
Customer migrations are very complex and costly from the network provider point of view. Not only does additional hardware and capacity have to be ordered, but customers also must be notified of the inevitable service interruption. Lengthy migration strategies and tools must also be developed in order to move customers from one device to another. Additionally, to replace network hardware with state-of-the-art equipment includes major capital costs.
The challenge for network operators is to extend the operational life of their deployed networks and obviate the hardware upgrade/replacement cycle. In order to achieve this, a system and method is needed that allows a network operator to disassociate line card forwarding table growth from the ability of a router to maintain service.